package leetcodev1.数组;

import java.util.Arrays;

public class Solution1 {

    //进行常规排序 官方不允许
    public void sortColors1(int[] nums) {
        Arrays.sort(nums);
    }

    //基数排序
    //统计每个颜色的个数，然后在循环进行赋值
    public void sortColors2(int[] nums) {
        int zeroNum = 0;
        int oneNum = 0;
        int twoNum = 0;

        for (int i : nums) {
            switch (i) {
                case 0:
                    ++zeroNum;
                    break;
                case 1:
                    ++oneNum;
                    break;
                case 2:
                    ++twoNum;
                    break;
                default:
            }
        }

        for (int i = 0; i < zeroNum; i++) {
            nums[i] = 0;
        }

        for (int i = 0; i < oneNum; i++) {
            nums[zeroNum + i] = 1;
        }

        for (int i = 0; i < twoNum; i++) {
            nums[zeroNum + oneNum + i] = 2;
        }
    }

    //只有三种颜色
    public void sortColors3(int[] nums) {
        int redLastIndex = 0, blueStarIndex = nums.length - 1;
        for (int i = 0; i <= blueStarIndex; i++) {
            if (nums[i] == 0) {
                int tmp = nums[redLastIndex];
                nums[redLastIndex++] = nums[i];
                nums[i] = tmp;
            } else if (nums[i] == 2) {
                int tmp = nums[blueStarIndex];
                nums[blueStarIndex--] = nums[i];
                nums[i] = tmp;
                // 避免遗漏 swap后重新检查一次
                i--;
            }
        }
    }

    //优化代码
    //[0,redLastIndex]红色
    //[redLastIndex+1,blueStarIndex)白色
    //[blueStarIndex,nums.length]蓝色
    public void sortColors4(int[] nums) {
        int redLastIndex = -1, blueStarIndex = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                redLastIndex += 1;
                int tmp = nums[redLastIndex];
                nums[redLastIndex] = nums[i];
                nums[i] = tmp;
            } else if (nums[i] == 2) {
                blueStarIndex -= 1;
                int tmp = nums[blueStarIndex];
                nums[blueStarIndex] = nums[i];
                nums[i] = tmp;
            }
        }
    }

    //输出数组中第k个大的数
    //小根堆
    //笨办法，全排序后选nums[k]
    public int findKthLargest1(int[] nums, int k) {
        if (nums == null || nums.length == 0 || nums.length < k) {
            return -1;
        }

        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    public int findKthLargest2(int[] nums, int k) {
        //校验入参
        if (nums == null || nums.length == 0 || nums.length < k) {
            return -1;
        }
        //从小到大
        int[] heap = new int[k];
        for (int i = 0; i < k; i++) {
            heap[i] = Integer.MIN_VALUE;
        }

        for (int num : nums) {
            //重新排序
            if (num > heap[0]) {
                //重新排序
                int j = 1;
                while (j < k && num > heap[j]) {
                    heap[j - 1] = heap[j];
                    j++;
                }
                heap[j - 1] = num;
            }
        }

        return heap[0];
    }

    //递归 分治
    //渐进的二分法
    public int findKthLargest3(int[] nums, int k) {
        return selection(nums, 0, nums.length - 1, nums.length - k);
    }

    //1.数组
    //2.左指针
    //3.右指针
    //4.第k个元素
    private int selection(int[] nums, int l, int r, int c) {
        //返回分解符的顺序
        int q = partion(nums, l, r);//默认数组中第一个 整个数组中的排名
        if (q == c) {
            return nums[q];
        } else {
            //在左边 | 右边 递归继续找
            return q < c ? selection(nums, q + 1, r, c) : selection(nums, l, q - 1, c);
        }
    }

    private int partion(int[] arr, int l, int r) {
        int pivot = arr[l];//分界元素
        int sp = l + 1;//左指针
        int bigger = r;//右指针
        //避免交叉 动态的遍历中
        while (sp <= bigger) {
            if (arr[sp] <= pivot) {
                sp++;//左指针++
            } else {
                swap(arr, sp, bigger);//交换当前指针
                bigger--;//右指针--
            }
        }
        swap(arr, l, bigger);//交换到合适的位置 把左右两部分有序
        return bigger;//返回排名

    }

    //swap
    private void swap(int[] arr, int sp, int bigger) {
        int temp = arr[sp];
        arr[sp] = arr[bigger];
        arr[bigger] = temp;
    }


}
